In the fields of image analysis and image compression, there are many applications for segmented images. As used herein, a segmented image is one which is made up of contiguous solid areas each having a single color and intensity. An example may be a cartoon drawing or a low-resolution version of a real-world image that is formed by reducing the real-world image to a collection of bounded areas and replacing each bounded area by its average value.
These images are useful for many different purposes. For example, object recognition in robot vision most closely mimics some aspects of human vision when the scene containing the objects is simplified into a segmented image. In addition, video compression applications in which an image may be subject to several cycles of compression and expansion may benefit from an image representation having, as a base component, a segmented image with well defined edges.
Another application for segmented images is digital image transmission. When, for example, a database of images is to be searched through a low-bandwidth channel, it may be desirable to provide a low-resolution image as the first step and then add detail to complete the image. Using this technique, a user may quickly determine, based only on the low-resolution component, if this is an image to be viewed. If not, the. display of the image may be aborted before a significant amount of data has been transmitted through the channel.
One exemplary system for forming segmented images is disclosed in a paper by Vincent et al. entitled "Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, Jun. 1991, pp 583-598. Another exemplary system is disclosed in a paper by T. Vlachos et al. entitled "Graph Theoretical Approach to Colour Picture Segmentation and Contour Classification" IEEE Proceedings-I vol 140, No. 1, Feb. 1993.
While each of these papers describes a method for generating a segmented image, neither addresses how such an image may be encoded for efficient storage. It is well known that a segmented image may be encoded using a chain-code technique. For example, the operation of an eight-chain is described in a paper by H. Freeman entitled "Computer Processing of Line Drawings" Computer Surveys, Vol. 6, No. 1, pp 57-97, March 1974, which is hereby incorporated by reference for its teachings on chain coding. The output data produced by this coder is a set of lists. Each list describes one area of constant color and constant brightness in the segmented image.
The entire set of lists describes the entire segmented image.
The algorithm assumes that an image is composed of discrete picture elements (pixels). To be effectively encoded using a chain code, the segmented image is desirably formed from discrete sets of contiguous pixel values, each set having a single luminance value, Y, and a single pair of color difference values, U and V. No particular method of forming the image is assumed; it may be raster scanned or generated from vectors.
Each list produced by the eight-chain code algorithm defines its area with a pair of color difference values, a luminance value for the area and an outline of the area. The outline begins and ends at a single pixel position. Only the address of this single starting pixel is contained in the list. Each other element of the outline portion of the list is a direction, relative to the current pixel, in which the next border pixel is to be found. This code is termed an eight-chain code because each element in the outline list may be one of eight directions, up, up-right, right, down-right, down, down-left, left and up-left relative to the current pixel.
The eight-chain code representation includes an element for each border pixel of each region in the image. Briefly, to generate an eight-chain code representation of a raster-scanned segmented image, the raster image is scanned until a border pixel is located. The address of this pixel is recorded in the list. The surrounding pixels are then scanned in a predetermined order to determine in which direction the next border pixel lies. This direction is recorded in the list. The identified next pixel then becomes the current pixel and its surrounding pixels are scanned to locate the next border pixel. The scanning of the surrounding pixels is in a predetermined rotational direction, either clockwise or counterclockwise, such that the last pixel scanned is the previous border pixel. For abutting regions, the pixels on each side of the actual border are members of separate outline lists for a chain-code representation of an image.
Since each border pixel of each region is encoded by a chain-code algorithm, a border between two regions is encoded twice, once for each region. Thus, a chain-code representation of an image contains almost twice the number of pixels that are needed to describe all of the edges.
A crack encoding system such as described in the book by A. Rosenfeld et al. entitled Digital Picture Processing, Academic Press, New York, NY which is hereby incorporated by reference for its teachings on crack coding is another type of coding system which operates in a manner similar to a chain coding system. A crack coder encodes the image region outlines by defining the borders, or cracks, between adjoining regions. It encodes the these borders in four directions, up, right, down and left.
While, for a given image, a crack code representation of an image may be more compact than a chain code representation of the image, it is still not well suited for some types of digital image processing applications. For example, in the image database application described above, it would be desirable to be able to view a low-resolution version of an entire image based on data contained in a single packet or in a small number of packets transmitted over a network. While chain coding or crack coding may produce significant data reduction, neither technique can ensure that a segmented image can be reconstructed from a fixed amount of data.